package com.dylan.历史.领扣;

import java.util.ArrayList;
import java.util.List;

/**
 * @Auther: ankang
 * @Date: 2019/2/22 14:50
 * @Description:
 */
public class $0057插入区间 {



    static class Solution {
        public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
            if (intervals.isEmpty()) {
                intervals.add(newInterval);
                return intervals;
            }
            boolean merge = false;
            for (int i = intervals.size() - 1; i >= 0; i--) {
                Interval curr = intervals.get(i);
                if (merge) {
                    Interval next = intervals.get(i + 1);
                    if (curr.end >= next.start) {
                        curr.start = curr.start < next.start ? curr.start : next.start;
                        curr.end = curr.end < next.end ? next.end : curr.end;
                        intervals.remove(i + 1);
                    } else {
                        break;
                    }
                } else {
                    if (newInterval.start > curr.end) {
                        intervals.add(i + 1, newInterval);
                        break;
                    } else if (newInterval.end >= curr.start) {
                        curr.start = curr.start < newInterval.start ? curr.start : newInterval.start;
                        curr.end = curr.end < newInterval.end ? newInterval.end : curr.end;
                        merge = true;
                    }
                }
            }
            return intervals;
        }
    }
    static class Interval {
        int start;
        int end;
        Interval() { start = 0; end = 0; }
        Interval(int s, int e) { start = s; end = e; }
    }
}
